//Given two sorted arrays nums1 and nums2 of size m and n respectively, return 
//the median of the two sorted arrays. 
//
// The overall run time complexity should be O(log (m+n)). 
//
// 
// Example 1: 
//
// 
//Input: nums1 = [1,3], nums2 = [2]
//Output: 2.00000
//Explanation: merged array = [1,2,3] and median is 2.
// 
//
// Example 2: 
//
// 
//Input: nums1 = [1,2], nums2 = [3,4]
//Output: 2.50000
//Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
// 
//
// Example 3: 
//
// 
//Input: nums1 = [0,0], nums2 = [0,0]
//Output: 0.00000
// 
//
// Example 4: 
//
// 
//Input: nums1 = [], nums2 = [1]
//Output: 1.00000
// 
//
// Example 5: 
//
// 
//Input: nums1 = [2], nums2 = []
//Output: 2.00000
// 
//
// 
// Constraints: 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
// Related Topics Array Binary Search Divide and Conquer 👍 13397 👎 1755


package leetcode.editor.en;

public class _4_MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new _4_MedianOfTwoSortedArrays().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if (nums1.length>nums2.length) {
                int[] temp = nums1;
                nums1 = nums2;
                nums2 = temp;
            }

            int leftTotal = (nums1.length + nums2.length + 1) / 2;
            int l = 0, r = nums1.length;
            while (l<r){
                int mid = l + (r - l + 1) / 2;
                int j = leftTotal - mid;
                if (nums1[mid-1]>nums2[j]){
                    r = mid-1;
                }else {
                    l = mid;
                }
            }
            int j = leftTotal - l;

            int num1leftMax = l==0?Integer.MIN_VALUE:nums1[l-1];
            int num1rightMin = l==nums1.length?Integer.MAX_VALUE:nums1[l];
            int num2leftMax = j==0?Integer.MIN_VALUE:nums2[j-1];
            int num2leftMin = j==nums2.length?Integer.MAX_VALUE:nums2[j];
            if ((nums1.length+nums2.length)%2==1){
                return Math.max(num1leftMax, num2leftMax);
            }
            return (double) (Math.max(num1leftMax, num2leftMax)+Math.min(num1rightMin, num2leftMin))/2;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}